1. Field of the Invention
The present invention is concerned with pattern recognition devices.
2. Related Art
Pattern recognition devices commonly receive, in digital form, an input pattern of bits which is then processed to produce a scalar value, or a number of such values, which are regarded as a vector. These may then be subjected to a thresholding operation to provide an output indicating the nature of an unknown pattern supplied to the device. Many such devices are learning devices, in that they are not constructed to recognize particular patterns but are, before use, supplied with training patterns, the output of the device being compared with information as to the nature of the pattern, or identifying a class to which it belongs, and the comparison result used as feedback to vary parameters stored within the device.
It is convenient to view such systems in terms of an input space and an output space. For example, one which receives a set of five scalar values and produces two scalar values may be considered as performing a mapping from a point in a five-dimensional input pattern space to a point in a two-dimensional output space.
One form of recognition device which has been proposed is the perceptron, which forms one or more weighted sums of a set of input values, the weighting factors being varied adaptively during the learning process. The main disadvantage of these is their inability to perform non-linear mappings from the input space to the output space, so that they cannot learn such apparently simple functions as the exclusive-or function. A solution to this problem is the multi-level percepton, where the output of a first layer of perceptrons supplies the input to a second layer; however, large amounts of training are required in order to learn quite simple non-linear mappings (i.e. convergence is slow), and this has made the application of multi-layer perceptions to real problems such as speech recognition very difficult.
Another form of recognition device is described in our European patent application Ser. No. 0183389B, and U.S. Pat. No. 4,782,459. This, as shown in FIG. 1, has an input store 1 in which an input vector having sixteen elements of 8-bits each are stored. Groups ("n-tuples") of bits are taken to form n-bit addresses for each of a number of random access memories 2, and the contents of the memory locations thereby addressed are added in an adder 3 to form a scalar output. During training, this output is compared in a subtractor 4 with the desired output input thereto, and the difference used to control updating of the memory contents. One application of the arrangement shown is as an echo canceller for telecommunications applications where the store 1 is in the form of a shift register receiving successive digitally coded temporal samples of a transmitted signal, the object of the device being to learn a mapping which models the echo characteristics of a transmission path.
As will be explained in greater detail below, the ability of such a recognition device to generalize from examples given in training depends to some extent upon the form in which the input data within the store 1 is coded. It is of course conventional to employ binary coding to represent digital values of a signal, but (as discussed in "Guide to pattern and recognition using random-access memories"- Aleksander and Stonham, computers and digital techniques, February 1979, Vol 2 No 1, Page 36 "6.3 coding of physical data") this is not particularly suitable for this class of pattern recognition devices since signal values which are quite close in signal space are disproportionately far apart in Hamming distance. The authors there propose a Gray code (which employs the same number of bits as the binary code) to overcome this problem but note that this can lead to spurious results as widely differing input signal levels can be close in Hamming distance. They point out that the most suitable coding is a 1-in-N code (hereinafter referred to as a bar code), in which as many bits as there are signal levels are employed. This code suffers from neither of the above drawbacks. It is, however, very inefficient and can require a large amount of input space; for example, for input data having 256 levels (i.e. the typical output of an 8 bit digital to analog converter), a 256 bit wide input buffer is required--which is clearly impractical (the binary and Gray code versions require only 8 bits, of course).